{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Numbers At Most N Given Digit Set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #string #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #字符串 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: atMostNGivenDigitSet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大为 N 的数字组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个按&nbsp;<strong>非递减顺序</strong>&nbsp;排列的数字数组<meta charset=\"UTF-8\" />&nbsp;<code>digits</code>&nbsp;。你可以用任意次数&nbsp;<code>digits[i]</code>&nbsp;来写的数字。例如，如果<meta charset=\"UTF-8\" />&nbsp;<code>digits = ['1','3','5']</code>，我们可以写数字，如<meta charset=\"UTF-8\" />&nbsp;<code>'13'</code>,&nbsp;<code>'551'</code>, 和&nbsp;<code>'1351315'</code>。</p>\n",
    "\n",
    "<p>返回 <em>可以生成的小于或等于给定整数 <code>n</code> 的正整数的个数</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [\"1\",\"3\",\"5\",\"7\"], n = 100\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>\n",
    "可写出的 20 个数字是：\n",
    "1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [\"1\",\"4\",\"9\"], n = 1000000000\n",
    "<strong>输出：</strong>29523\n",
    "<strong>解释：</strong>\n",
    "我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，\n",
    "81 个四位数字，243 个五位数字，729 个六位数字，\n",
    "2187 个七位数字，6561 个八位数字和 19683 个九位数字。\n",
    "总共，可以使用D中的数字写出 29523 个整数。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [\"7\"], n = 8\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= digits.length &lt;= 9</code></li>\n",
    "\t<li><code>digits[i].length == 1</code></li>\n",
    "\t<li><code>digits[i]</code>&nbsp;是从&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code> 的数</li>\n",
    "\t<li><code>digits</code>&nbsp;中的所有值都 <strong>不同</strong>&nbsp;</li>\n",
    "\t<li><code>digits</code>&nbsp;按&nbsp;<strong>非递减顺序</strong>&nbsp;排列</li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [numbers-at-most-n-given-digit-set](https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [numbers-at-most-n-given-digit-set](https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"1\",\"3\",\"5\",\"7\"]\\n100', '[\"1\",\"4\",\"9\"]\\n1000000000', '[\"7\"]\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s=str(n)\n",
    "\n",
    "        @lru_cache()\n",
    "        def f(i,is_limit,is_num):\n",
    "            if i==len(s):\n",
    "                return is_num\n",
    "            \n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res+=f(i+1,False,False)\n",
    "            \n",
    "            low='0' if is_num else '1'\n",
    "            up=s[i] if is_limit else '9'\n",
    "\n",
    "            for d in digits:\n",
    "                if low<=d<=up:\n",
    "                    res+=f(i+1,is_limit and d==up ,True)\n",
    "            return res\n",
    "        return f(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            for d in digits:\n",
    "                if d == s[i - 1]:\n",
    "                    dp[i][1] = dp[i - 1][1]\n",
    "                elif d < s[i - 1]:\n",
    "                    dp[i][0] += dp[i - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        res = 0\n",
    "        length = len(digits)\n",
    "\n",
    "        s = str(n)\n",
    "        limit = len(s)\n",
    "\n",
    "        # 首先计算比目标位数少的\n",
    "        for i in range(1, limit):\n",
    "            res += length ** i\n",
    "\n",
    "        # 计算位数相等的情况\n",
    "        # 完全小于、完全等于\n",
    "        dp = [[0, 0] for _ in range(limit)]\n",
    "        for j, c in enumerate(s):\n",
    "            lower = 0\n",
    "            for d in digits:\n",
    "                if d < c:\n",
    "                    lower += 1\n",
    "                elif d == c:\n",
    "                    dp[j][1] = 1 if j < 1 else dp[j - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if j > 0:\n",
    "                dp[j][0] = dp[j-1][0] * length + dp[j - 1][1] * lower\n",
    "            else:\n",
    "                dp[j][0] = lower\n",
    "\n",
    "        res += sum(dp[-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i,is_limit,is_num):\n",
    "            if i==len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,False,False)\n",
    "            up = s[i] if is_limit else \"9\"\n",
    "            for d in digits:\n",
    "                if d>up:\n",
    "                    break\n",
    "                res += f(i+1,is_limit and d==up,True)\n",
    "            return res \n",
    "        return f(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            \n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += dfs(i+1, False, False)\n",
    "            \n",
    "            up = s[i] if is_limit else '9'\n",
    "\n",
    "            for d in digits:\n",
    "                if d > up: break\n",
    "                res += dfs(i+1, is_limit and d == s[i], True)\n",
    "            \n",
    "            return res\n",
    "        return dfs(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        nums = []\n",
    "        for ts in digits:\n",
    "            nums.append(int(ts))\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int :\n",
    "            if i==m:\n",
    "                return is_num\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            low = 0 if is_num else 1\n",
    "            for d in nums :\n",
    "                if d >= low and d <= up:\n",
    "                    res += f(i+1, is_limit and d==up ,True)\n",
    "            return res\n",
    "        return f(0, True, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if int(d) <= up:\n",
    "                    res += f(i+1, is_limit and d == s[i], True)\n",
    "            return res\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            for d in digits:\n",
    "                if d == s[i - 1]:\n",
    "                    dp[i][1] = dp[i - 1][1]\n",
    "                elif d < s[i - 1]:\n",
    "                    dp[i][0] += dp[i - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        max_digit = len(str(n))\n",
    "        res = 0\n",
    "        number = len(digits)\n",
    "        k = number\n",
    "        for i in range(1,max_digit):\n",
    "            res += k\n",
    "            k *= number\n",
    "        \n",
    "        \n",
    "        \n",
    "        target = [x for x in str(n)]\n",
    "\n",
    "        add = 0\n",
    "        \n",
    "        for i in range(max_digit):\n",
    "            cnt = 0\n",
    "            same = False\n",
    "            for ch in digits:\n",
    "                if ch < target[i]:\n",
    "                    cnt += 1\n",
    "                elif ch==target[i]:\n",
    "                    cnt += 1\n",
    "                    same = True\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "            #第(idx+1)位上，有cnt个小于等于n的，有可能有相等的\n",
    "            print(cnt, same)\n",
    "            if same and i<max_digit-1:\n",
    "                cnt -= 1\n",
    "                add += cnt*number**(max_digit-1-i)\n",
    "            elif same and i==max_digit-1:\n",
    "                add += cnt*number**(max_digit-1-i)\n",
    "                break\n",
    "            else:\n",
    "                add += cnt*number**(max_digit-1-i)\n",
    "                break\n",
    "        print(res,add)\n",
    "        return res+add\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        n = str(n)\n",
    "        l = len(n)\n",
    "        @cache\n",
    "        def dfs(i,flag,zero):\n",
    "            if i == l:\n",
    "                return 1 if zero == False else 0\n",
    "            if flag:\n",
    "                maxnum = int(n[i] )\n",
    "            else:\n",
    "                maxnum= 9\n",
    "            res = 0\n",
    "            if zero:\n",
    "                res += dfs(i+1,False,True)\n",
    "            for j in range(maxnum+1):\n",
    "                flagj = True if (j == maxnum and flag) else False\n",
    "                \n",
    "                if str(j) in digits:\n",
    "                    res += dfs(i+1,flagj,False)\n",
    "                \n",
    "            return res\n",
    "        \n",
    "        return dfs(0,True,True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            for d in digits:\n",
    "                if d == s[i - 1]:\n",
    "                    dp[i][1] = dp[i - 1][1]\n",
    "                elif d < s[i - 1]:\n",
    "                    dp[i][0] += dp[i - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        w = str(n)\n",
    "        m = len(w)\n",
    "        #is_num判断是否跳过，跳过是False，没跳过True，is_limit是否限制\n",
    "        @cache\n",
    "        def f(i,is_num,is_limit):\n",
    "            if i==m:\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "               res = f(i+1,False,False)\n",
    "            up = w[i] if is_limit else \"9\"\n",
    "            for d in digits:\n",
    "                if d>up:\n",
    "                    break\n",
    "                res+=f(i+1,True,is_limit and d==up)      \n",
    "            return res\n",
    "        return f(0,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i+1,False,False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d>up:\n",
    "                    break\n",
    "                res += dfs(i+1,is_limit and d==up,True)\n",
    "            return res\n",
    "        return dfs(0,True,False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        arr=str(n)\n",
    "        size=len(arr)\n",
    "        @cache\n",
    "        def f(i,skip,reach):\n",
    "            if i==size:\n",
    "                return 0 if skip else 1\n",
    "            limit=int(arr[i]) if reach else 9\n",
    "            ans=0\n",
    "            for d in digits:\n",
    "                if int(d)>limit:\n",
    "                    break\n",
    "                ans+=f(i+1,False,reach and int(d)==limit)\n",
    "            if skip:\n",
    "                ans+=f(i+1,True,False)\n",
    "            return ans\n",
    "        return f(0,True,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits = [int(i) for i in digits]\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == n:\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if is_num == 0:\n",
    "                res = f(i + 1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if int(d) > up:\n",
    "                    break\n",
    "                res += f(i + 1, is_limit and (int(d) == up), True)\n",
    "            return res\n",
    "        return f(0, True, False)                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i:int,is_limit:bool,is_num:bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,False,False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += f(i+1, is_limit and d==up, True)\n",
    "            return res\n",
    "        return f(0,True,False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(idx, bound, empty):\n",
    "            if idx == n: return int(not empty)\n",
    "            res = 0 \n",
    "            if empty:\n",
    "                res += dfs(idx+1, None, True)\n",
    "            # up = num[idx] if bound else '9'\n",
    "            for d in digits:\n",
    "                if not bound or d <= num[idx]:\n",
    "                    res += dfs(idx+1, d == num[idx] and bound, False)\n",
    "            return res\n",
    "\n",
    "        num = str(n)\n",
    "        n = len(num)\n",
    "        ret = dfs(0, True, True)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        if n < 10:\n",
    "            result = 0\n",
    "            for d in digits:\n",
    "                if int(d) <= n:\n",
    "                    result += 1\n",
    "            return result\n",
    "        mx = len(str(n)) - 1\n",
    "        result = 0\n",
    "        tmp = 1\n",
    "        for i in range(mx):\n",
    "            tmp *= len(digits)\n",
    "            result += tmp\n",
    "        hd = n // 10**mx\n",
    "        for d in digits:\n",
    "            if int(d) < hd:\n",
    "                result += tmp\n",
    "            elif int(d) == hd:\n",
    "                result += self.sub(digits, n % 10**mx, mx)\n",
    "        return result\n",
    "    \n",
    "    def sub(self, digits, n, ln):\n",
    "        if ln <= 1:\n",
    "            return self.atMostNGivenDigitSet(digits, n)\n",
    "        mx = ln - 1\n",
    "        hd = n // 10**mx\n",
    "        result = 0\n",
    "        for d in digits:\n",
    "            if int(d) < hd:\n",
    "                result += len(digits)**mx\n",
    "            elif int(d) == hd:\n",
    "                result += self.sub(digits, n % 10**mx, ln - 1)\n",
    "        return result\n",
    "\n",
    "# 4 + 16 + 64 + 4 * 64 + "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1  # 初始化 dp[0][1] = 1，表示没有选择任何数字，当前数字等于 n 的前 0 位\n",
    "        \n",
    "        for i in range(1, k + 1):\n",
    "            for d in digits:\n",
    "                # 当前数字 d 等于 n 的第 i 位，我们可以在前 i - 1 位相等的情况下，选择 d 作为第 i 位，继续保持相等\n",
    "                if d == s[i - 1]:\n",
    "                    dp[i][1] = dp[i - 1][1]\n",
    "                # 当前数字 d 小于 n 的第 i 位，我们可以在前 i - 1 位相等的情况下，选择 d 作为第 i 位，使新数字小于 n\n",
    "                elif d < s[i - 1]:\n",
    "                    dp[i][0] += dp[i - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "            # 当 i > 1 时，我们可以考虑小于 n 的前 i 位的数字，这些数字可以通过在前 i - 1 位的任意数字后追加一个 d 构成\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False)\n",
    "            \n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up: break\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0,0] for _ in range(k+1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(k):\n",
    "            for d in digits:\n",
    "                if d == s[i]:\n",
    "                    dp[i+1][1] = dp[i][1]\n",
    "                elif d < s[i]:\n",
    "                    dp[i+1][0] += dp[i][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 0: # 位数小于k才加，所以从第2位才开始\n",
    "                dp[i+1][0] += (dp[i][0]+1)*m\n",
    "        return sum(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(digits)\n",
    "        # s = str(n)\n",
    "        # k = len(s)\n",
    "        # dp = [[0, 0] for _ in range(k + 1)]\n",
    "        # dp[0][1] = 1\n",
    "        # for i in range(k):\n",
    "        #     for d in digits:\n",
    "        #         if d == s[i]:\n",
    "        #             dp[i+1][1] = dp[i][1]\n",
    "        #         elif d < s[i]:\n",
    "        #             dp[i+1][0] += dp[i][1]\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     if i > 0:\n",
    "        #         dp[i+1][0] += (dp[i][0]+1) * m\n",
    "        # return sum(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m=len(digits)\n",
    "\n",
    "        s=str(n)\n",
    "        nums=[int(c) for c in s]\n",
    "        n=len(nums)\n",
    "        pick=[int(x) for x in digits]\n",
    "\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=nums[i]\n",
    "            cur=bisect_right(pick,x)-1\n",
    "            if cur==-1:\n",
    "                break \n",
    "            elif pick[cur]==x:\n",
    "                ans+=cur*m**(n-i-1)\n",
    "                if i==n-1:\n",
    "                    ans+=1\n",
    "            elif pick[cur]<x:\n",
    "                ans+=(cur+1)*m**(n-i-1)\n",
    "                break\n",
    "        \n",
    "        cur=1\n",
    "        for i in range(n-1):\n",
    "            cur*=m\n",
    "            ans+=cur\n",
    "        return ans\n",
    "        \n",
    "\n",
    "                    \n",
    "                \n",
    "        \n",
    "        \n",
    "                \n",
    "                \n",
    "        # def dfs(cur):\n",
    "        #     nonlocal ans\n",
    "        #     if len(cur)==lenth and int(cur)<=n:\n",
    "        #         ans+=1\n",
    "        #         return\n",
    "        #     for i in range(m):\n",
    "        #         dfs(cur+digits[i])\n",
    "        # dfs(\"\")\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        # m=len(digits)\n",
    "        # res=0\n",
    "        # @cache\n",
    "        # def dfs(cur):\n",
    "        #     nonlocal res\n",
    "        #     if cur and int(cur)>n:\n",
    "        #         return 0\n",
    "        #     else:\n",
    "        #         res+=1\n",
    "        #     for i in range(m):\n",
    "        #         dfs(cur+digits[i])\n",
    "        # dfs(\"\")\n",
    "        # return res-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0,0] for _ in range(k+1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1,k+1):\n",
    "            for d in digits:\n",
    "                if d == s[i-1]:\n",
    "                    dp[i][1] = dp[i-1][1]\n",
    "                elif d < s[i-1]:\n",
    "                    dp[i][0] += dp[i-1][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i-1][0]*m\n",
    "        return sum(dp[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        n_len = 1\n",
    "        tn = n+0\n",
    "        ll_num = []\n",
    "        while tn>9:\n",
    "            n_len+=1\n",
    "            ll_num.append(tn%10)\n",
    "            tn = tn//10\n",
    "        ll_num.append(tn)\n",
    "        ll_digits = len(digits)\n",
    "        def cum(t_num, len_num):\n",
    "            if len_num==0:\n",
    "                return 0\n",
    "            num = 1\n",
    "            while len_num>0:\n",
    "                len_num-=1\n",
    "                num = num*t_num\n",
    "            return num\n",
    "        num = 0\n",
    "        ll_n = n_len-1\n",
    "        while ll_n>0:\n",
    "            num+=cum(ll_digits, ll_n)\n",
    "            ll_n-=1\n",
    "\n",
    "        def delnum(num):\n",
    "            tt = 0\n",
    "            ll = False\n",
    "            for i in range(ll_digits):\n",
    "                if int(digits[i])<num:\n",
    "                    tt+=1\n",
    "                if int(digits[i])==num:\n",
    "                    ll=True\n",
    "            return tt,ll\n",
    "        \n",
    "        if n_len==1:\n",
    "            t1,l1 = delnum(n)\n",
    "            return t1 if not l1 else t1+1\n",
    "        for i in range(n_len):\n",
    "            t_i, ll = delnum(ll_num[-i-1])\n",
    "            if i==n_len-1:\n",
    "                if ll:\n",
    "                    num += t_i+1\n",
    "                else:\n",
    "                    num += t_i\n",
    "            else:\n",
    "                num += t_i*cum(ll_digits, n_len-i-1)\n",
    "            if not ll:\n",
    "                break\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        n = str(n)\n",
    "        s = set(digits)\n",
    "        @cache\n",
    "        def dfs(i, isNum, isLimit):\n",
    "            if i == len(n): return int(isNum)\n",
    "            ans = dfs(i + 1, False, False) if not isNum else 0\n",
    "            lower = 0 if isNum else 1\n",
    "            upper = int(n[i]) if isLimit else 9\n",
    "            for x in range(lower, upper + 1):\n",
    "                if str(x) in s:\n",
    "                    ans += dfs(i + 1, True, isLimit and x == upper)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == m:\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1, False, False)\n",
    "            upper = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if int(d) <= upper:\n",
    "                    res += f(i + 1, is_limit and int(d) == upper, True)\n",
    "            return res\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        # 根据分析，使用数位dp时，mask没用\n",
    "        s = str(n)\n",
    "        @lru_cache(None)\n",
    "        def f(i:int,is_limit:bool,is_num:bool):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,False,False) \n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d <= up:\n",
    "                    res += f(i+1,is_limit and d==up,True)\n",
    "            return res\n",
    "        return f(0,True,False) \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 有想法了，但是模板没掌握\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "        @cache\n",
    "        def dfs(i,is_num,is_limit):\n",
    "            if i == m:return int(is_num)\n",
    "            # 不填\n",
    "            res = 0\n",
    "            # 前面没填过才能够不填数字\n",
    "            if not is_num:\n",
    "                res =  dfs(i+1,False,False)\n",
    "            # 填\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up:break\n",
    "                res += dfs(i+1,True,is_limit and d == up)\n",
    "            return res\n",
    "        return dfs(0,False,True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i + 1, False, False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += dfs(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits = [int(x) for x in digits]\n",
    "        @cache\n",
    "        def dfs(i, islimit, isnum) :\n",
    "            if i == len(s) :\n",
    "                return 1\n",
    "            res = 0\n",
    "            #不选\n",
    "            if not isnum :\n",
    "                res = dfs(i + 1, False, False)\n",
    "            up = int(s[i]) if islimit else 9\n",
    "            #选\n",
    "            for d in digits :\n",
    "                if int(d) > up : \n",
    "                    break\n",
    "                res += dfs(i + 1, islimit and d == up, True)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, True, False) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dp(i: int, limited: bool, chosen: bool):\n",
    "            if i==len(s): return int(chosen)\n",
    "            res = 0\n",
    "            if not chosen:\n",
    "                res += dp(i+1, False, False)\n",
    "            up = s[i] if limited else '9'\n",
    "            for d in digits:\n",
    "                if d>up: break\n",
    "                res += dp(i+1, limited and d==up, True)\n",
    "            return res\n",
    "        return dp(0, True, False)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        res = 0\n",
    "        m = len(digits)\n",
    "        num = list(str(n))\n",
    "\n",
    "        digits = list(map(int, digits))\n",
    "        num = list(map(int, num))\n",
    "\n",
    "        for i in range(len(num)-1):\n",
    "            res += pow(m, i+1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(level, isLimit):\n",
    "            if level == len(num):\n",
    "                return 1\n",
    "            \n",
    "            max_v = 9\n",
    "            if isLimit:\n",
    "                max_v = num[level]\n",
    "            \n",
    "            res = 0\n",
    "            for i in range(len(digits)):\n",
    "                if digits[i] <= max_v:\n",
    "                    res += dfs(level+1, isLimit and digits[i] == max_v)\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return res + dfs(0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0 if is_num else dfs(i + 1, False, False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(low, up + 1):\n",
    "                if str(d) in digits: \n",
    "                    res += dfs(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "\n",
    "        return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], limit: int) -> int:\n",
    "        s = str(limit)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i==n:\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            \n",
    "            if not is_num:\n",
    "                res = dfs(i+1, False, False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d  in digits:\n",
    "                if d<=up:\n",
    "                    res += dfs(i+1, is_limit and (d==up), True)\n",
    "            return res\n",
    "        return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        # 函数返回res：从第i位开始填数字可以组成的符合要求的数字个数\n",
    "        # i：当前为第i位\n",
    "        # is_limit: 前面的数字是否已经是极限，用于判断当前位可取数字的上限up，如果为true则上限为int(s[i])，若为false则上限为9\n",
    "        # is_num：前面已经确定的数字是否有效，若为true则下限down为0,若为false则可跳过或者下限为1\n",
    "        def find_nb(i: int, is_limit: bool, is_num: bool)->int:\n",
    "            # 看是否已经判断完\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "\n",
    "            up = s[i] if is_limit else '9'\n",
    "            \n",
    "            if not is_num:\n",
    "                res += find_nb(i+1, False, False)\n",
    "\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += find_nb(i+1, is_limit and d == s[i], True)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return find_nb(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        # 数位dp，lc2376\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == len(s): return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1, False, False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up: break\n",
    "                res += f(i+1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False) \n",
    "\n",
    "        # m, s = len(digits), str(n)\n",
    "        # k = len(s)\n",
    "        # # dp[i][0] 表示由digits构成小于n的前i位数字的个数, dp[i][1] 为等于n的前i位\n",
    "        # dp = [[0, 0] for _ in range(k + 1)]\n",
    "        # dp[0][1] = 1\n",
    "        # for i in range(1, k + 1):\n",
    "        #     for d in digits:\n",
    "        #         if d == s[i - 1]:\n",
    "        #             dp[i][1] = dp[i - 1][1]\n",
    "        #         elif d < s[i - 1]:\n",
    "        #             dp[i][0] += dp[i - 1][1]\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     if i > 1:\n",
    "        #         dp[i][0] += m + dp[i - 1][0] * m  # 第i位有m种选择, +m表示前缀为0的单字符\n",
    "        # return sum(dp[k])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0,0] for _ in range(k+1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(k):\n",
    "            for d in digits:\n",
    "                if d == s[i]:\n",
    "                    dp[i+1][1] = dp[i][1]\n",
    "                elif d < s[i]:\n",
    "                    dp[i+1][0] += dp[i][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 0:\n",
    "                dp[i+1][0] += (dp[i][0]+1)*m\n",
    "        return sum(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(digits)\n",
    "        # s = str(n)\n",
    "        # k = len(s)\n",
    "        # dp = [[0, 0] for _ in range(k + 1)]\n",
    "        # dp[0][1] = 1\n",
    "        # for i in range(k):\n",
    "        #     for d in digits:\n",
    "        #         if d == s[i]:\n",
    "        #             dp[i+1][1] = dp[i][1]\n",
    "        #         elif d < s[i]:\n",
    "        #             dp[i+1][0] += dp[i][1]\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     if i > 0:\n",
    "        #         dp[i+1][0] += (dp[i][0]+1) * m\n",
    "        # return sum(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s): return int(is_num)  # 如果填了数字，则为 1 种合法方案\n",
    "            res = 0\n",
    "            if not is_num:  # 前面不填数字，那么可以跳过当前数位，也不填数字\n",
    "                # is_limit 改为 False，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束\n",
    "                # is_num 仍然为 False，因为没有填任何数字\n",
    "                res = f(i + 1, False, False)\n",
    "            up = s[i] if is_limit else '9'  # 根据是否受到约束，决定可以填的数字的上限\n",
    "            # 注意：对于一般的题目而言，如果此时 is_num 为 False，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况\n",
    "            for d in digits:  # 枚举要填入的数字 d\n",
    "                if d > up: break  # d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环\n",
    "                # is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束\n",
    "                # is_num 为 True，因为填了数字\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        # 位数\n",
    "        n_count = len(str(n))\n",
    "        res = 0\n",
    "        n_digits = len(digits)\n",
    "        def A(a,b):\n",
    "            return a**b\n",
    "        for i in range(n_count-1,0,-1):\n",
    "            a = n_count-i # 第a位数 1,2...n_count-1\n",
    "            res +=A(n_digits,a)\n",
    "        def getcount(i,n):\n",
    "            if(i==n_count):\n",
    "                return 1\n",
    "            num = int(str(n)[i])\n",
    "            smaller_count = len([a for i in digits if (a:=int(i)) < num])\n",
    "            tmp = smaller_count*A(n_digits,n_count-i-1)\n",
    "            if f\"{num}\" in digits:\n",
    "                tmp+=getcount(i+1,n)\n",
    "            return tmp\n",
    "        res+=getcount(0,n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits = set(digits)\n",
    "        @cache\n",
    "        def helper(i, is_num, is_limit):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ret = 0\n",
    "            if not is_num:\n",
    "                ret = helper(i + 1, False, False)\n",
    "            \n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(0 if is_num else 1, up + 1):\n",
    "                if str(d) in digits:\n",
    "                    ret += helper(i + 1, True, d == up and is_limit)\n",
    "            return ret\n",
    "        return helper(0, False, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, isLimit: bool, isNum: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return 1 if isNum else 0\n",
    "            upper = s[i] if isLimit else '9'\n",
    "            ans = 0\n",
    "            if not isNum:\n",
    "                ans += f(i + 1, False, False)\n",
    "            for d in digits:\n",
    "                if d > upper:\n",
    "                    break\n",
    "                ans += f(i + 1, isLimit and d == s[i], True)\n",
    "            return ans\n",
    "\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        # 数位dp\n",
    "        s = str(n)\n",
    "\n",
    "        # 返回从i开始填数字，i前面填的数字,能构造出的特殊整数的数目\n",
    "        # is_limit 表示前面填的数字是否都是n对应位上的，如果为true，那么当前位至多是int(s[i]),\n",
    "        # 否则至多为9\n",
    "        # is_num 表示前面是否填了数字(是否跳过),如果为true,那么当前位可以从0开始，如果为false,\n",
    "        # 那么我们可以跳过，或者从1开始填数字\n",
    "        @lru_cache\n",
    "        def f(i: int, is_limit:bool, is_num:bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num: # 选择跳过，不填数字\n",
    "                res=f(i+1, False, False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            # 枚举要填的数字，枚举的范围就取决于is_limit 和 is_num\n",
    "            for d in digits:\n",
    "                if d>up: break\n",
    "                res += f(i+1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            if dp[i-1][1] == 1:\n",
    "                for d in digits:\n",
    "                    if d == s[i - 1]:\n",
    "                        dp[i][1] = dp[i - 1][1]\n",
    "                    elif d < s[i - 1]:\n",
    "                        dp[i][0] += dp[i - 1][1]\n",
    "                    else:\n",
    "                        break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        ls = len(s)\n",
    "        lend = len(digits)\n",
    "        dp = [[0,0] for _ in range(ls)]\n",
    "\n",
    "        # 第一个数字，s[0]\n",
    "        for i in range(ls):\n",
    "            if i == 0:\n",
    "                dp[i][0] = len([x for x in digits if x < s[i]])\n",
    "                dp[i][1] = int(s[i] in digits)\n",
    "            else:\n",
    "                dp[i][1] = int(dp[i-1][1] and s[i] in digits)\n",
    "                dp[i][0] = (dp[i-1][0]+1) * lend + dp[i-1][1] * len([x for x in digits if x < s[i]])\n",
    "\n",
    "        return dp[ls-1][0] + dp[ls-1][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "          if i == l:\n",
    "             return is_num\n",
    "          res = 0\n",
    "          if not is_num:\n",
    "             res += dfs(i + 1, False, False)\n",
    "          up = int(s[i]) if is_limit else 9\n",
    "          for j in digits:\n",
    "             if int(j) > up:\n",
    "                break\n",
    "             res += dfs(i + 1, is_limit and int(j) == up, True)\n",
    "          return res\n",
    "       s = str(n)\n",
    "       l = len(s)\n",
    "       return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = list(map(int, str(n)))\n",
    "        n = len(s)\n",
    "        digits = list(map(int, digits))\n",
    "\n",
    "        @cache\n",
    "        def fun(idx, is_num, is_limit):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            if not is_num: \n",
    "                res += fun(idx + 1, False, False)\n",
    "             \n",
    "            lower = 0 if is_num else 1\n",
    "            higher = s[idx] if is_limit else 9\n",
    "            for i in range(lower, higher + 1):\n",
    "                if i in digits:\n",
    "                    res += fun(idx + 1, True, i == higher and is_limit)\n",
    "            return res\n",
    "        \n",
    "        return fun(0, False, True) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num):\n",
    "            if i==m:\n",
    "                return is_num\n",
    "            ans=0\n",
    "            if not is_num:\n",
    "                ans+=dfs(i+1,False,False)\n",
    "            minv=0 if is_num else 1\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            for j in digits:\n",
    "                if int(j)<minv:\n",
    "                    continue\n",
    "                if int(j)>maxv:\n",
    "                    break\n",
    "                ans+=dfs(i+1,is_limit and int(j)==maxv,True)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if int(d) <= up:\n",
    "                    res += f(i+1, is_limit and int(d) == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            if dp[i-1][1] == 1:\n",
    "                for d in digits:\n",
    "                    if d == s[i - 1]:\n",
    "                        dp[i][1] = dp[i - 1][1]\n",
    "                    elif d < s[i - 1]:\n",
    "                        dp[i][0] += dp[i - 1][1]\n",
    "                    else:\n",
    "                        break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        digits=sorted(digits) #将数码进行排序\n",
    "        l=len(str(n)) #位数\n",
    "        ans=0\n",
    "        for i in range(1,l):\n",
    "            ans += len(digits) ** (l - i) #先将少一位的全组合情况统计好\n",
    "            \n",
    "        def count(n,p):\n",
    "            if p==len(str(n)):#如果位数超过了，返回1种情况\n",
    "                return 1\n",
    "            cnt=0\n",
    "            for j in digits: #在当前p位置遍历数码\n",
    "                if j < str(n)[p]: #如果当前数码小于目标位置\n",
    "                    cnt += len(digits) ** (len(str(n)) - p-1) #后续位数全组合情况直接计算 \n",
    "                elif j == str(n)[p]: #如果当前数码等于目标位置，需要深搜来判断后续位的组合数量\n",
    "                    cnt+=count(n,p+1)\n",
    "            return cnt\n",
    "        ans+=count(n,0)\n",
    "        return ans\n",
    "\n",
    "# 今天这个dp做真的有点难，我自己用深搜做其实还算比较好理解。原理就是判断从最高位开始判断，数码中有几个小于目标位置的，其实只要高位是小于目标位置的，后几位就可以随意的组合，可以用数学计算出来，唯一要处理的就是，如果有一位是等于的，就要判断后续位不大于的情况有几种，可以对后面位依次进行深搜判断"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        ds, ts = [int(d) for d in digits], []\n",
    "        while n > 0:\n",
    "            ts.append(n % 10)\n",
    "            n //= 10\n",
    "        res, m = {}, len(ds)\n",
    "        def get(idx, st):\n",
    "            if idx == -1: return 1\n",
    "            if st == 0: return m ** (idx + 1)\n",
    "            ret = 0\n",
    "            for d in ds:\n",
    "                if d < ts[idx]: ret += get(idx - 1, 0)\n",
    "                elif d == ts[idx]: ret += get(idx - 1, 1)\n",
    "            return ret\n",
    "        ans = get(len(ts) - 1, 1)\n",
    "        for idx in range(len(ts) - 1): ans += get(idx, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in [int(x) for x in digits if int(x) <= up]:  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            if dp[i-1][1] == 1:\n",
    "                for d in digits:\n",
    "                    if d == s[i - 1]:\n",
    "                        dp[i][1] = dp[i - 1][1]\n",
    "                    elif d < s[i - 1]:\n",
    "                        dp[i][0] += dp[i - 1][1]\n",
    "                    else:\n",
    "                        break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m\n",
    "        return sum(dp[k])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], limit: int) -> int:\n",
    "        s = str(limit)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i==n:\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            \n",
    "            if not is_num:\n",
    "                res = dfs(i+1, False, False)\n",
    "            up = -1\n",
    "            if is_limit:\n",
    "                for ind, digit in enumerate(digits):\n",
    "                    if int(digit)<=int(s[i]):\n",
    "                        up = ind\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                up = len(digits)-1\n",
    "            for d in range(up+1):\n",
    "                res += dfs(i+1, is_limit and (digits[d]==s[i]), True)\n",
    "            return res\n",
    "        return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s): return int(is_num)  # 如果填了数字，则为 1 种合法方案\n",
    "            res = 0\n",
    "            if not is_num:  # 前面不填数字，那么可以跳过当前数位，也不填数字\n",
    "                # is_limit 改为 False，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束\n",
    "                # is_num 仍然为 False，因为没有填任何数字\n",
    "                res = f(i + 1, False, False)\n",
    "            up = s[i] if is_limit else '9'  # 根据是否受到约束，决定可以填的数字的上限\n",
    "            # 注意：对于一般的题目而言，如果此时 is_num 为 False，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况\n",
    "            for d in digits:  # 枚举要填入的数字 d\n",
    "                if d > up: break  # d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环\n",
    "                # is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束\n",
    "                # is_num 为 True，因为填了数字\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in digits:\n",
    "                if int(d) <= up:\n",
    "                    res += f(i+1, is_limit and int(d) == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i,is_limit,is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1,False,False)\n",
    "            up = s[i] if is_limit else \"9\"\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += f(i + 1,is_limit and d == up,True)\n",
    "            return res\n",
    "        return f(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s): return int(is_num)  # 如果填了数字，则为 1 种合法方案\n",
    "            res = 0\n",
    "            if not is_num:  # 前面不填数字，那么可以跳过当前数位，也不填数字\n",
    "                # is_limit 改为 False，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束\n",
    "                # is_num 仍然为 False，因为没有填任何数字\n",
    "                res = f(i + 1, False, False)\n",
    "            up = s[i] if is_limit else '9'  # 根据是否受到约束，决定可以填的数字的上限\n",
    "            # 注意：对于一般的题目而言，如果此时 is_num 为 False，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况\n",
    "            for d in digits:  # 枚举要填入的数字 d\n",
    "                if d > up: break  # d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环\n",
    "                # is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束\n",
    "                # is_num 为 True，因为填了数字\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        ns = str(n)\n",
    "        m = len(ns)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(j,flag,cnt):            \n",
    "            if j >= m:\n",
    "                return int(cnt >= 1)\n",
    "            ans = 0\n",
    "            if cnt == 0:\n",
    "                ans += f(j+1,False,cnt)\n",
    "            for i in range(len(digits)):\n",
    "                if flag:\n",
    "                    if digits[i] < ns[j]:\n",
    "                        ans += f(j+1,False,cnt+1)\n",
    "                    elif digits[i] == ns[j]:\n",
    "                        ans += f(j+1,True,cnt+1)\n",
    "                else:\n",
    "                    ans += f(j+1,False,cnt+1)\n",
    "            # print(j,flag,cnt,ans)\n",
    "            return ans\n",
    "        return f(0,True,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i,is_limit,is_num):\n",
    "            if i == len(s):\n",
    "                return is_num\n",
    "            \n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,False,False)\n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up:\n",
    "                    break\n",
    "                res += f(i+1,is_limit and up==d,True)\n",
    "            return res\n",
    "        return f(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s): return int(is_num)  # 如果填了数字，则为 1 种合法方案\n",
    "            res = 0\n",
    "            if not is_num:  # 前面不填数字，那么可以跳过当前数位，也不填数字\n",
    "                # is_limit 改为 False，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束\n",
    "                # is_num 仍然为 False，因为没有填任何数字\n",
    "                res = f(i + 1, False, False)\n",
    "            up = s[i] if is_limit else '9'  # 根据是否受到约束，决定可以填的数字的上限\n",
    "            # 注意：对于一般的题目而言，如果此时 is_num 为 False，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况\n",
    "            for d in digits:  # 枚举要填入的数字 d\n",
    "                if d > up: break  # d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环\n",
    "                # is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束\n",
    "                # is_num 为 True，因为填了数字\n",
    "                res += f(i + 1, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits = set([int(x) for x in digits])\n",
    "        @cache\n",
    "        def dfs(i,is_num,is_limit):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ans = 0\n",
    "            if not is_num:\n",
    "                ans = dfs(i + 1,False,False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            low = 0 if is_num else 1\n",
    "            for x in range(low,up + 1):\n",
    "                if x not in digits:\n",
    "                    continue\n",
    "                ans += dfs(i + 1,True,is_limit and x == up)\n",
    "            return ans\n",
    "        return dfs(0,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        bits = []\n",
    "        is_limit = True\n",
    "        for c in s:\n",
    "            if not is_limit:\n",
    "                bits.append(m - 1)\n",
    "                continue\n",
    "            select_index = -1\n",
    "            for j, d in enumerate(digits):\n",
    "                if d > c:\n",
    "                    break\n",
    "                select_index = j\n",
    "            if select_index >= 0:\n",
    "                bits.append(select_index)\n",
    "                if digits[select_index] < c:\n",
    "                    is_limit = False\n",
    "            else:\n",
    "                sz = len(bits)\n",
    "                while bits and bits[-1] == 0:\n",
    "                    bits.pop()\n",
    "                if bits:\n",
    "                    bits[-1] -= 1\n",
    "                else:\n",
    "                    sz -= 1\n",
    "                while len(bits) <= sz:\n",
    "                    bits.append(m - 1)\n",
    "                is_limit = False\n",
    "        ans = 0\n",
    "        for b in bits:\n",
    "            ans = ans * m + b + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num):\n",
    "            if i==len(s):\n",
    "                return int(is_num)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res=dfs(i+1,False,False)\n",
    "\n",
    "            if is_limit:\n",
    "                up=s[i]\n",
    "            else:\n",
    "                up='9'\n",
    "            \n",
    "            for d in digits:\n",
    "                if d >up:\n",
    "                    break\n",
    "                else:\n",
    "                    res+=dfs(i+1,is_limit and d==up,True)\n",
    "            return res\n",
    "        return dfs(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        def cal(s : str) -> int:\n",
    "            @cache\n",
    "            def f(i : int,is_limit : bool,is_num : bool) -> int:\n",
    "                \"\"\"\n",
    "                i: 当前数位\n",
    "                is_limit: 仅能在digits内取数填充\n",
    "                is_num: 是否填过数\n",
    "                return: 返回小于等于n的仅由digits内的数构成的数的个数\n",
    "                \"\"\"\n",
    "                if i == len(s):\n",
    "                    return int(is_num)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1,False,False)\n",
    "                up = s[i] if is_limit else '9'\n",
    "                for d in digits:\n",
    "                    if d > up: break\n",
    "                    res += f(i + 1,is_limit and d == up,True)\n",
    "                return res\n",
    "            return f(0,True,False)\n",
    "        return cal(str(n)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def atMostNGivenDigitSet(self, digits, n):\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dp(i,limit ,is_num):\n",
    "            if i==len(s):\n",
    "                return int(is_num)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res+=dp(i+1,False,False)\n",
    "            up=s[i] if limit else '9'\n",
    "            for digit in digits:\n",
    "                \n",
    "                if digit >up:\n",
    "                    break\n",
    "                res+=dp(i+1,limit and up==digit,True)\n",
    "            return res\n",
    "        return dp(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        num = len(digits)\n",
    "        count = 0\n",
    "        i = 1\n",
    "        while n/(10**(i-1))>=10:\n",
    "            count += self.get_C(num,i)\n",
    "            i += 1\n",
    "        # i=3\n",
    "        n_str = str(n)\n",
    "        j = 0\n",
    "        def get_match_num(digits,i,j,n_str):\n",
    "            count = 0\n",
    "            if digits[j] > n_str[0]:\n",
    "                return count\n",
    "            elif digits[j] < n_str[0]:\n",
    "                count += self.get_C(num,i-1)\n",
    "                j += 1\n",
    "                if j < len(digits):\n",
    "                    #print(j,digits)\n",
    "                    count += get_match_num(digits,i,j,n_str)\n",
    "                return count\n",
    "            elif digits[j] == n_str[0]:\n",
    "                i -= 1\n",
    "                j = 0\n",
    "                n_str = n_str[1:]\n",
    "                if j < len(digits) and n_str!='':\n",
    "                    print(j,digits,n_str)\n",
    "                    count += get_match_num(digits,i,j,n_str)\n",
    "                else:\n",
    "                    count += 1\n",
    "                return count\n",
    "\n",
    "        return count + get_match_num(digits,i,j,n_str)\n",
    "        \n",
    "    \n",
    "    def get_C(self,a,b):\n",
    "        res = 1\n",
    "        if b == 0 or a == 0:\n",
    "            return 1\n",
    "        for _ in range(b):\n",
    "            res = res * a\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        strn = str(n)\n",
    "\n",
    "        @functools.cache\n",
    "        def helper(i):\n",
    "            index = bisect.bisect_right(digits, strn[i])\n",
    "            if i == len(strn) - 1:\n",
    "                return index\n",
    "            if strn[i] == 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if index > 0:\n",
    "                if digits[index -1] == strn[i]:\n",
    "                    ans += (index - 1) * (len(digits) ** (len(strn) -i - 1)) + helper(i+1)\n",
    "                else:\n",
    "                    ans += (index) * (len(digits) ** (len(strn) -i - 1))\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, len(strn)):\n",
    "            ans += len(digits) ** i\n",
    "        ans += helper(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        m = len(digits)\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        dp = [[0, 0] for _ in range(k + 1)]\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            for d in digits:\n",
    "                if d == s[i - 1]:\n",
    "                    dp[i][1] = dp[i - 1][1]\n",
    "                elif d < s[i - 1]:\n",
    "                    dp[i][0] += dp[i - 1][1]\n",
    "                else:\n",
    "                    break\n",
    "            if i > 1:\n",
    "                dp[i][0] += m + dp[i - 1][0] * m \n",
    "        return sum(dp[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits = [int(x) for x in digits]\n",
    "        @cache\n",
    "        def dfs(i, islimit, isnum) :\n",
    "            if i == len(s) :\n",
    "                return 1\n",
    "            res = 0\n",
    "            #不选\n",
    "            if not isnum :\n",
    "                res = dfs(i + 1, False, False)\n",
    "            up = int(s[i]) if islimit else 9\n",
    "            #选\n",
    "            for d in digits :\n",
    "                if d > up : \n",
    "                    break\n",
    "                res += dfs(i + 1, islimit and d == up, True)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, True, False) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        self.s = list(str(n))\n",
    "        self.n = n\n",
    "        self.digits = digits\n",
    "        return self.solve(0, True, False)\n",
    "\n",
    "\n",
    "    @cache\n",
    "    def solve(self, i, is_limit, is_num):\n",
    "        if i == len(self.s):\n",
    "            return int(is_num)\n",
    "        \n",
    "        up = self.s[i] if is_limit else '9'\n",
    "        res = 0\n",
    "        if not is_num:\n",
    "            res += self.solve(i+1, False, False)\n",
    "        for d in self.digits:\n",
    "            if d > up:\n",
    "                break\n",
    "            res += self.solve(i+1, is_limit & (d == up), True)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "\n",
    "        @cache\n",
    "        def f(i, equal, zeros):\n",
    "            if i == m:\n",
    "                return 1 if not zeros else 0\n",
    "            ans = 0\n",
    "            if zeros:\n",
    "                ans += f(i+1, False, True)\n",
    "            for x in digits:\n",
    "                if not equal or x <= s[i]:\n",
    "                    ans += f(i+1, equal & (x == s[i]), False)\n",
    "            return ans\n",
    "\n",
    "        return f(0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num):\n",
    "            if i==m:\n",
    "                return is_num\n",
    "            ans=0\n",
    "            if not is_num:\n",
    "                ans+=dfs(i+1,False,False)\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            for j in digits:\n",
    "                if int(j)>maxv:\n",
    "                    break\n",
    "                ans+=dfs(i+1,is_limit and int(j)==maxv,True)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num):\n",
    "            if i==m:\n",
    "                return is_num\n",
    "            ans=0\n",
    "            if not is_num:\n",
    "                ans+=dfs(i+1,False,False)\n",
    "            maxv=s[i] if is_limit else '9'\n",
    "            for j in digits:\n",
    "                if j>maxv:\n",
    "                    break\n",
    "                ans+=dfs(i+1,is_limit and j==maxv,True)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, is_limit: bool, is_skip: bool) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if is_skip:\n",
    "                res += f(i + 1, False, True)\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in [int(x) for x in digits if int(x) <= up]:  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, is_limit and d == up, False)\n",
    "            return res\n",
    "        return f(0, True, True) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        # is_limit表示当前可选的位数i的取数范围是否受限，不受限就是0-9，受限就是0-s[i]\n",
    "        # is_num表示i前面的位数是否填了数字，填了就可以从0开始，否则从1开始\n",
    "        # dfs(i, is_limit, is_num)代表从左往右第i位及其后面的数位的合法种类数\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_num): \n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i+1, False, False)\n",
    "            \n",
    "            up = s[i] if is_limit else '9'\n",
    "            for d in digits:\n",
    "                if d > up: break\n",
    "\n",
    "                res += dfs(i+1, is_limit and d == up, True)\n",
    "            \n",
    "            return res \n",
    "        \n",
    "        return dfs(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        k  = str(n)\n",
    "        #is_num跳过\n",
    "        @cache\n",
    "        def f(i,is_limit,is_num):\n",
    "            if i==len(k):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not  is_num:\n",
    "                res = f(i+1,False,False)\n",
    "            up = k[i] if is_limit else \"9\"\n",
    "            for d in digits:\n",
    "                if d>up:\n",
    "                    break\n",
    "                res+=f(i+1,is_limit and d==up,True)\n",
    "            return res\n",
    "        return  f(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        # 函数f返回前i个数位可组成的数字数量\n",
    "        def f(i, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            \n",
    "            res = 0\n",
    "            up = s[i] if is_limit else '9'\n",
    "\n",
    "            if not is_num:\n",
    "                res = f(i+1, False, False)\n",
    "            \n",
    "            for j in digits:\n",
    "                if j > up:\n",
    "                    break\n",
    "                \n",
    "                res += f(i+1, True if j == up and is_limit else False, True)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return f(0, True, False)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(pos, lead, limit):\n",
    "            if pos <= 0:\n",
    "                return lead == False\n",
    "            up = a[pos] if limit else 9\n",
    "            ans = 0\n",
    "            for i in range(up + 1):\n",
    "                if i == 0 and lead:\n",
    "                    ans += dfs(pos - 1, lead, limit and i == up)\n",
    "                elif i in s:\n",
    "                    ans += dfs(pos - 1, False, limit and i == up)\n",
    "            return ans\n",
    "\n",
    "        l = 0\n",
    "        a = [0] * 12\n",
    "        s = {int(d) for d in digits}\n",
    "        while n:\n",
    "            l += 1\n",
    "            a[l] = n % 10\n",
    "            n //= 10\n",
    "        return dfs(l, True, True)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
